package leetcode;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
/**
 * 290.单词规律
 * 输入: pattern = "abba", str = "dog cat cat dog"
 * 输出: true
 */
public class Num_290 {

    /** 方法一：时间复杂度高 **/
    public boolean wordPattern(String pattern, String s) {
        String[] data1 = s.split(" ");
        String[] data2 = pattern.split("");

        String str1 = change(data1);
        String str2 = change(data2);

        if(str1.equals(str2)){
            return true;
        }else{
            return false;
        }
    }
    //将字符串数组化简
    public String change(String[] data){
        int[] x = new int[data.length];
        int a = 97;
        //化简字符串数组
        for(int i=0; i<data.length; i++){
            if(x[i] == 0){ //确保第i个字符串没有改变过
                String c = "";
                c += (char) a; //c是字母
                for(int j=i+1; j< data.length; j++){
                    if(x[j]==0 && data[i].equals(data[j])){
                        data[j] = c;
                        x[j] = 1;
                    }
                }
                //改变第i个字符串的值
                data[i] = c;
                x[i] = 1;
                a ++;
            }
        }
        return Arrays.toString(data);
    }

    /** 方法二：双映射，用HashMap，时间复杂度低 **/
    public boolean wordPattern2(String pattern, String s){

        String[] data = s.split(" ");

        //先判断拆分后长度是否相同
        if(pattern.length() != data.length){
            return false;
        }

        //两条HashMap存放字符和字符串之间的双映射关系
        Map<Character,String> map1 = new HashMap<>();
        Map<String,Character> map2 = new HashMap<>();

        //循环每一组，使其形成映射关系
        for(int i=0; i<data.length; i++){

            //Character -> String
            if(map1.containsKey(pattern.charAt(i))){
                if(!map1.get(pattern.charAt(i)).equals(data[i])){
                    return false;
                }
            }else{
                map1.put(pattern.charAt(i),data[i]);
            }

            //String -> Character
            if(map2.containsKey(data[i])){
                if(!map2.get(data[i]).equals(pattern.charAt(i))){
                    return false;
                }
            }else{
                map2.put(data[i],pattern.charAt(i));
            }
        }
        return true;
    }

}
